package MyListNode;

public class Leetcode0025 {
    public static ListNode reverse(ListNode start) {
        ListNode pre = null;
        ListNode pos = start;

        while (pos != null){
            ListNode after = pos.next;
            pos.next = pre;
            pre = pos;
            pos = after;

        }
        return pre;
    }
    public static ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null){
            return head;
        }
        //定义一个假的节点
        //假节点的next指向head。
        // dummy->1->2->3->4->5
        ListNode dump = new ListNode(-1);
        dump.next = head;
        //初始化pre和end都指向dummy。
        // pre指每次要翻转的链表的头结点的上一个节点。
        // end指每次要翻转的链表的尾节点
        ListNode pre = dump;
        ListNode end = dump;

        while (end.next!=null){
            for(int i=1; i<=k && end!=null;i++){
                // end 待反转这节的结尾
                end = end.next;
            }
            //如果end==null，即需要翻转的链表的节点数小于k，不执行翻转。
            if(end==null){
                break;
            }
            // 待反转这节的开头
            ListNode start = pre.next;
            // 下一节的开头
            ListNode after = end.next;
            end.next = null;

            // 将反转的部分头部 和 尾部 分别结起来
            // 翻转链表,pre.next指向翻转后的链表。
            // 1->2 变成2->1。 dummy->2->1
            pre.next = reverse(start);
            start.next = after;
            // 更改末尾指针
            pre = start;
            end = pre;
        }
        return dump.next;
    }

}
